
pub fn min_edge_prime_num(number: u32) -> String {
    // 将百分比转换为小数
    let target_ratio = (number as f64) / 100.0;
    let mut edge_length: i64 = 3; // 起始边长
    let mut diagonal_count: i64 = 5; // 对角线上的数字个数
    let mut prime_count: i64 = 3; // 对角线上的素数个数

    // 检查初始的对角线数字 (1, 3, 5, 7, 9)
    // for &n in &[1, 3, 5, 7, 9] {
    //     if is_prime(n) {
    //         prime_count += 1;
    //     }
    // }
    

    loop {
        // 计算当前比例
        let ratio = prime_count as f64 / diagonal_count as f64;
        // 小于目标比例则退出
        if ratio < target_ratio {
            break;
        }

        // 扩展螺旋 找出四个角上的数
        edge_length += 2;
        let corner1 = edge_length * edge_length;
        let corner2 = corner1 - (edge_length - 1);
        let corner3 = corner2 - (edge_length - 1);
        let corner4 = corner3 - (edge_length - 1);

        // 检查四个角是否为素数
        for corner in [corner4, corner3, corner2] {
            if is_prime(corner) {
                prime_count += 1;
            }
        }

        diagonal_count += 4;
    }

    format!("{},{}", edge_length, prime_count)
}

fn qpow(mut a: i64, mut n: i64, p: i64) -> i64 {
    let mut ans = 1i64;
    while n > 0 {
        if (n & 1) == 1 {
            ans = (ans as i128 * a as i128 % p as i128) as i64;
        }
        a = (a as i128 * a as i128 % p as i128) as i64;
        n >>= 1;
    }
    ans
}

fn is_prime_small(num: i64) -> bool {
    // 处理特殊情况
    if num <= 1 {
        return false;
    }
    // 处理小素数
    if num <= 7 {
        return [2, 3, 5, 7].contains(&num);
    }
    // 快速检查能否被小素数整除
    if num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0 {
        return false;
    }

    let sqrt_num = (num as f64).sqrt() as i64;
    // 使用6k±1优化
    let mut i = 11;
    while i <= sqrt_num {
        // 检查6k-1形式的数
        if num % i == 0 {
            return false;
        }
        // 检查6k+1形式的数
        if num % (i + 2) == 0 {
            return false;
        }
        i += 6;
    }

    true
}

fn is_prime_large(x: i64) -> bool {
    if x < 3 {
        return x == 2;
    }
    if x % 2 == 0 {
        return false;
    }
    
    let bases = [2i64, 325, 9375, 28178, 450775, 9780504, 1795265022];
    let mut d = x - 1;
    let mut r = 0;
    
    while d % 2 == 0 {
        d /= 2;
        r += 1;
    }
    
    for &a in bases.iter() {
        if a >= x {
            continue;
        }
        
        let mut v = qpow(a, d, x);
        if v <= 1 || v == x - 1 {
            continue;
        }
        
        let mut is_composite = true;
        for i in 0..r {
            v = (v as i128 * v as i128 % x as i128) as i64;
            if v == x - 1 && i != r - 1 {
                v = 1;
                is_composite = false;
                break;
            }
            if v == 1 {
                return false;
            }
        }
        if is_composite && v != 1 {
            return false;
        }
    }
    true
}

pub fn is_prime(num: i64) -> bool {
    const THRESHOLD: i64 = 50_000_000;
    
    if num <= THRESHOLD {
        is_prime_small(num)
    } else {
        is_prime_large(num)
    }
}


// fn is_prime(num: i64) -> bool {
//     // 处理特殊情况
//     if num <= 1 {
//         return false;
//     }
//     // 处理小素数
//     if num <= 7 {
//         return [2, 3, 5, 7].contains(&num);
//     }
//     // 快速检查能否被小素数整除
//     if num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0 {
//         return false;
//     }

//     let sqrt_num = (num as f64).sqrt() as i64;
//     // 使用6k±1优化
//     let mut i = 11;
//     while i <= sqrt_num {
//         // 检查6k-1形式的数
//         if num % i == 0 {
//             return false;
//         }
//         // 检查6k+1形式的数
//         if num % (i + 2) == 0 {
//             return false;
//         }
//         i += 6;
//     }

//     true
// }


